package com.sort;

import java.util.Arrays;

/**
 * @BelongsProject: DataStructures
 * @BelongsPackage: com.sort
 * @Author: 江岸
 * @CreateTime: 2021-01-30 18:21
 * @Description: 插入排序
 */
public class InsertSort {

    public static void main(String[] args) {
        //        int[] arr = {5,42,78,11,37,894,131,-1};
        int[] arr = new int[80000];
        for (int i=0;i<arr.length;i++){
            arr[i] = (int) (Math.random()*800000);
        }
        long l = System.currentTimeMillis();
        int insertVal;
        int insertIndex;
        for (int i = 1;i<arr.length;i++){
             insertVal = arr[i];
             insertIndex = i - 1;
            while (insertIndex >= 0 && insertVal < arr[insertIndex] ){
                arr[insertIndex+1] = arr[insertIndex];
                insertIndex -- ;
            }
            arr[insertIndex+1] = insertVal;
        }
        long l1 = System.currentTimeMillis();
        System.out.println((l1-l));
    }
}
